package binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import utils.binaryTreeUtil;
import utils.binaryTreeUtil.TreeNode;

public class pathSum {
    // List<List<Integer>> list = new ArrayList();
    // //没办法解决重复节点的问题  eg：10 5 3 3     10 5 3 -2
    // public int pathSum(TreeNode root, int targetSum) {
    //     preOrder(root, 0, new ArrayList<>());
    //     int count = 0;
    //     for (List<Integer> subList : list) {
    //         int[] prefixSum = new int[subList.size()];
    //         preSum(prefixSum, subList);
    //         for (int i = 0; i < prefixSum.length; i++) {
    //             for (int j = i; j < prefixSum.length; j++) {
    //                 if (i == j) {
    //                     if (prefixSum[i] == targetSum) {
    //                         count++;
    //                     }
    //                 } else {
    //                     if (prefixSum[j] - prefixSum[i] == targetSum) {
    //                         //可能有重合
    //                         //10 5 3 3     10 5 3 -2
    //                         count++;
    //                     }
    //                 }
    //             }
    //         }
    //     }
    //     return count;
    // }

    // public void preOrder(TreeNode node, int depth, List<Integer> subList) {
    //     if (node==null) {
    //         return;
    //     }
    //     if (node.left == null && node.right == null) {
    //         // 防止重复
    //         subList.add(node.val);
    //         list.add(new ArrayList<>(subList));
    //         subList.remove(depth);
    //         return;
    //     }
    //     subList.add(node.val);
    //     preOrder(node.left, depth + 1, subList);
    //     preOrder(node.right, depth + 1, subList);
    //     subList.remove(depth);
    // }

    // public void preSum(int[] nums, List<Integer> list) {
    //     nums[0] = list.get(0);
    //     for (int i = 1; i < nums.length; i++) {
    //         nums[i] = nums[i - 1] + list.get(i);
    //     }
    // }

    //定义每个起点
    int ret=0;
    
    public int pathSum(TreeNode root, int targetSum) {
    
        if (root==null) {
            return 0;
        }
        ret+=rootSum(root, targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ret;
    }
    //计算的是剩余值
    public int rootSum(TreeNode root,int targetSum){
        if (root==null) {
            return 0;
        }
        int count=0;
        if (root.val==targetSum) {
            count++;
        }
        count += rootSum(root.left, targetSum-root.val);
        count += rootSum(root.right, targetSum-root.val);

        return count;
    }
    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 10, 5, -3, 3, 2, null, 11, 3, -2, null, 1 };
        TreeNode tree = binaryTreeUtil.buildTree(arr);
        pathSum p = new pathSum();
        System.out.println(p.pathSum(tree, 8));
    }
}
